package com.zj.leetcode.hard.greed;

/**
 * @program: algorithm
 * @description: 超级洗衣机
 * 517 super-washing-machines
 * @author: Zhang Bo
 * @create: 2022-04-02 11:46:29
 **/
public class SuperWashingMachines {
    public static void main(String[] args) {
        int[] machines = {4, 0, 0, 4};
        Solution solution = new SuperWashingMachines().new Solution();
        System.out.println(solution.findMinMoves(machines));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {


        /**
         * [1,0,5] 3
         * [1,9,5,13] 6
         * <p>
         * [1,5,9,13] 8
         * [4,0,0,4] 2
         * 贪心算法
         *
         * @param machines
         * @return
         */
        public int findMinMoves(int[] machines) {

            long total = 0;
            int length = machines.length;
            for (int i = 0; i < length; i++) {
                total += machines[i];
            }
            if (total % length != 0) {
                return -1;
            }

            int count = 0;
            long mid = total / length;

            if (mid == 0) {
                return 0;
            }
            for (int i = 1; i < length; i++) {
                long num1 = Math.abs(machines[i - 1] - mid);
                long num2 = Math.abs(machines[i] - mid);
                long max = Math.max(num1, num2);
                if (machines[i - 1] / mid < 0) {
                    machines[i] = (int) (machines[i] - (mid - machines[i - 1] % mid));
                } else {
                    machines[i] = (int) (machines[i - 1] - mid + machines[i]);
                }
                count = Math.max((int) max, count);
            }

            return count;
        }


        public int findMinMoves01(int[] machines) {
            int sum = 0;
            for(int num : machines)
                sum += num;
            if(sum % machines.length != 0)
                return -1;

            int target = sum / machines.length;
            int res = 0, balance = 0;
            for(int i = 0 ; i < machines.length; i ++){
                balance += machines[i] - target;
                res = Math.max(res, Math.max(machines[i] - target, Math.abs(balance)));
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
